package divide_and_conquer;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/57rwmg/
public class LCR_134Pow {
    //分治法
    class Solution {
        public double myPow(double x, int n) {
            if(x == 0.0f) return 0.0d;
            double res = 1.0;
            long b = n; // 使用长整型来避免整数溢出
            if(b < 0) {
                x = 1 / x;
                b = -b;
            }
            while(b > 0) {
                if(b%2 == 1) res *= x;
                x *= x;
                b /= 2;
            }
            return res;
        }
    }
    //递归
    class Solution2 {
        public double myPow(double x, long n) {// 使用长整型来避免整数溢出
            if(n == 0) return 1;
            if(n < 0) return 1/myPow(x,-n);
            if(n%2 == 1) return x * myPow(x*x,n/2);
            else return myPow(x*x,n/2);
        }
    }
}
